\documentclass[11pt]{report}

%IMPORTANTE comando \hyphenation{ma-cro-istru-zio-ne nitro-idrossil-amminico} definisce all'algoritmo di latex come spezzare una parola non presente nel suo vocabolario!!

%INCLUSIONE DI PACCHETTI
\usepackage{graphicx}
\usepackage{rotating}
\usepackage{array}
\usepackage{longtable}
\usepackage{multirow}
\usepackage{wrapfig} 
\usepackage{lastpage}
\usepackage{fancyhdr}
\usepackage[english]{babel}
\usepackage{amssymb}
%\usepackage[T1]{fontenc}
%\usepackage[latin9]{inputenc}
\usepackage[colorlinks=true]{hyperref} %per indice con link alle pagine
\usepackage[a4paper,portrait,left=2.5cm,right=2.5cm,bindingoffset=5mm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{color}
%\usepackage{xstring}
\hypersetup{colorlinks,citecolor=black,filecolor=black,linkcolor=red,urlcolor=blue}
\setcounter{secnumdepth}{2} % per numerare anche \subsubsection
\setcounter{tocdepth}{2}% per farlo apparire nell'indice
\frenchspacing
\definecolor{LightMagenta}{cmyk}{0.1,0.8,0,0.1}


%HEADER e FOOTER di tutte le pagine tranne quella in cui compare il titolo del capitolo
\pagestyle{fancy}
\fancyhead{}
\headheight = 54pt
\lhead{Computer Science Theory II}
\lfoot{}
\cfoot{}
\rfoot{Page \thepage{ of} \pageref{LastPage}}
\renewcommand{\headrulewidth}{1pt}
\renewcommand{\footrulewidth}{1pt}
\rhead{\nouppercase{\leftmark}}
\renewcommand{\chaptermark}[1]{\markboth{\thechapter.\ #1}{}}

%HEADER e FOOTER della pagina dove compare il titolo del capitolo
\fancypagestyle{plain}{
%\lhead{\includegraphics[height=50pt]{images/logoUniPd.png}} %IN ALTO A SINISTRA (POTREBBE ANDARE BENE IL LOGO)
\chead{}
\rhead{\bfseries WS2011/12}%\manualeUtenteVer} %IN ALTO A DESTRA
\lfoot{
\begin{tabular}{lc}
Victor A. Arrascue Ayala & Mtr. 3209050\\
Tobias Domhan  & Mtr.  3202957 \\
\end{tabular}
}
\cfoot{}
\rfoot{Page \thepage{ of} \pageref{LastPage}}
\renewcommand{\headrulewidth}{1pt}
\renewcommand{\footrulewidth}{1pt}
}

\fancypagestyle{romano}{
\lhead{}
\chead{}
\rhead{}
\lfoot{}
\cfoot{\thepage}
\rfoot{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
}

\fancypagestyle{empty}{
\lhead{}
\chead{}
\rhead{}
\lfoot{}
\cfoot{}
\rfoot{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
}

%PAGINA DI PRESETAZIONE DEL DOCUMENTO
\hyphenation{}
\begin{document}


%\begin{center}
%\thispagestyle{empty}
%\huge\textbf{UNIVERSIT\`A degli Studi di PADOVA}\\[2 cm] %GRUPPO DI APPARTENENZA
%\vspace*{0.5in}
%\LARGE\textbf{Titolo del documento}\\[1.0 cm] %TITOLO DEL DOCUMENTO
%\par\rule{10cm}{.5pt} \par
%{\large 12 Ottobre 2009}   %DATA DI CREAZIONE
%\par\rule{10cm}{.10pt} \par
%\vspace*{1.0in}
%\includegraphics[scale=0.30]{images/logoUniPd.png} \\[2cm] %LOGO GRUPPO
%\Large\textbf{Michele Tonon} %AUTORE
%\par\rule{6cm}{.5pt} \par
%\end{center}



% INDEX
%\newpage
%\thispagestyle{romano}
%\pagenumbering{arabic}
%\tableofcontents


%--------------------------------------------- 


%CONTENT


\newpage
\thispagestyle{plain}

\begin{center}
{\Large \textbf{Exercise Sheet 11}}
\end{center}

\noindent{\textbf{Exercise 11.1}}\\\\
(a)\\
M is Turing Machine that decides the language \{0$^{n}$1$^{n}$ $\mid$ n $\geq$ 1\}.\\
M = ``On input string w:
\begin{enumerate}
\item If the leftmost tape symbol is a blank or 1 reject.
\item Place a mark X on top of the leftmost tape symbol. 
\item Go to the right until we find a 1 and place an X on top. If a blank symbol is reached without finding a 1 then reject.
\item Go to the left searching for a 0. If a 0 is found mark X on top and go to step 3. 
\item If no 0 is found in step 4 the pointer points at the beginning of the tape. Go to the right and check that all the symbols you read are marked with X until you reach the blank symbol. If this is the case accept, otherwise reject."
\end{enumerate}
(b) This is the sequence of configurations for the input string 0011:\\
q$_{i}$0011 $\rightarrow$ q$_{i}$X011 $\rightarrow$ Xq$_{i}$011 $\rightarrow$ X0q$_{i}$11 $\rightarrow$ X0q$_{i}$X1 $\rightarrow$ Xq$_{i}$0X1 $\rightarrow$ Xq$_{i}$XX1 $\rightarrow$ XXq$_{i}$X1 $\rightarrow$ XXXq$_{i}$1 $\rightarrow$ XXXq$_{i}$X $\rightarrow$ XXq$_{i}$XX $\rightarrow$ Xq$_{i}$XXX $\rightarrow$ q$_{i}$XXXX $\rightarrow$ Xq$_{i}$XXX $\rightarrow$ XXq$_{i}$XX $\rightarrow$ XXXq$_{i}$X $\rightarrow$ XXXXq$_{i}$\\
We are currently in step 5  and in the last configuration we read a blank symbol. Therefore, we accept. Note that q$_{i}$ represents a generic state of our Turing Machine.\\\\
(C) This is the sequence of configurations for the input string 0010:\\
q$_{i}$0010 $\rightarrow$ q$_{i}$X010 $\rightarrow$ Xq$_{i}$010 $\rightarrow$ X0q$_{i}$10 $\rightarrow$ X0q$_{i}$X0 $\rightarrow$ Xq$_{i}$0X0 $\rightarrow$ Xq$_{i}$XX0 $\rightarrow$ XXq$_{i}$X0 $\rightarrow$ XXXq$_{i}$0\\
We are currently in step 3 and in the last configuration we read a blank symbol because no 1 was found. Therefore, we reject. Again, q$_{i}$ represents a generic state of our Turing Machine.

\vspace{1cm}
\noindent{\textbf{Exercise 11.2}}\\\\

\vspace{1cm}
\noindent{\textbf{Exercise 11.3}}\\\\
We can simulate a PDA with a Non Deterministic Turing machine consisting of two tapes. As we have seen, a Multi-tape Turing machine is equivalent to a single-tape Turing machine.\\
\begin{itemize}
\item To first tape T$_{1}$ contains the input w.
\item The steps The second tape T$_{2}$ simulates the behavior of the stack. We can easily initialize the stack in the same way we do in a PDA by marking the beginning of T$_{2}$ with the symbol \$ before we start processing the input.
\item We keep the pointer of T$_{2}$ always on its right most element. Whenever we have a push, we replace the blank symbol next to it with the new symbol and move the pointer to the right. Whenever we have a pop, we replace the symbol pointed with a blank symbol and move the pointer to the left.  Whenever we have $\epsilon$ in a pop or push operation in the PDA we keep the pointer where it is and leave the pointed symbol as it is.
\item The computation is essentially the same in the Turing Machine for a given input, but push and pops on the stack are simulated in T$_{2}$ as explained in the previous point.
\end{itemize}
\vspace{1cm}
\noindent{\textbf{Exercise 11.4}}\\\\


\end{document}














